home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / msdos / raytrace / pov / bin / xtras / bound.c < prev    next >
C/C++ Source or Header  |  1994-09-11  |  25KB  |  953 lines
  1. /****************************************************************************
  2. *
  3. *  ATTENTION!!!
  4. *
  5. *  THIS FILE HAS BEEN MODIFIED!!! IT IS NOT PART OF THE OFFICAL
  6. *  POV-RAY 2.2 DISTRIBUTION!!!
  7. *
  8. *  THIS FILE IS PART OF "FASTER THAN POV-RAY" (VERSION 2.2),
  9. *  A SPED-UP VERSION OF POV-RAY 2.2. USE AT YOUR OWN RISK!!!!!!
  10. *
  11. *  New files: addon0.c, addon1.c, addon2.c, addon3.c, addon.h
  12. *
  13. *  The additional modules were written by Dieter Bayer.
  14. *
  15. *  Send comments, suggestions, bugs, ideas ... to:
  16. *
  17. *  e-mail: dieter@cip.e-technik.uni-erlangen.de
  18. *  CIS: 100255.3074
  19. *
  20. *  All changed/added lines are enclosed in #ifdef DB_CODE ... #endif
  21. *
  22. *  The vista projection was taken from:
  23. *
  24. *    A. Hashimoto, T. Akimoto, K. Mase, and Y. Suenaga, 
  25. *    "Vista Ray-Tracing: High Speed Ray Tracing Using Perspective
  26. *    Projection Image", New Advances in Computer Graphics, Proceedings
  27. *    of CG International '89, R. A. Earnshaw, B. Wyvill (Eds.), 
  28. *    Springer, ..., pp. 549-560
  29. *
  30. *  The idea for the light buffer was taken from:
  31. *
  32. *    E. Haines and D. Greenberg, "The Light Buffer: A Shadow-Testing 
  33. *    Accelerator", IEEE CG&A, Vol. 6, No. 9, Sept. 1986, pp. 6-16
  34. *
  35. *****************************************************************************/
  36.  
  37. /****************************************************************************
  38. *                bound.c
  39. *
  40. *  This module implements the bounding slab calculations.
  41. *  This file was written by Alexander Enzmann.    He wrote the code for
  42. *  POV-Ray's bounding slabs and generously provided us these enhancements.
  43. *  The slab intersection code was further hacked by Eric Haines to speed it up.
  44. *
  45. *  Just so everyone knows where this came from, the code is VERY heavily
  46. *  based on the slab code from Mark VandeWettering's MTV raytracer.
  47. *  POV-Ray is just joining the crowd of admirers of Mark's contribution to
  48. *  the public domain. [ARE]
  49. *
  50. *  from Persistence of Vision Raytracer
  51. *  Copyright 1993 Persistence of Vision Team
  52. *---------------------------------------------------------------------------
  53. *  NOTICE: This source code file is provided so that users may experiment
  54. *  with enhancements to POV-Ray and to port the software to platforms other
  55. *  than those supported by the POV-Ray Team.  There are strict rules under
  56. *  which you are permitted to use this file.  The rules are in the file
  57. *  named POVLEGAL.DOC which should be distributed with this file. If
  58. *  POVLEGAL.DOC is not available or for more info please contact the POV-Ray
  59. *  Team Coordinator by leaving a message in CompuServe's Graphics Developer's
  60. *  Forum.  The latest version of POV-Ray may be found there as well.
  61. *
  62. * This program is based on the popular DKB raytracer version 2.12.
  63. * DKBTrace was originally written by David K. Buck.
  64. * DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
  65. *
  66. *****************************************************************************/
  67.  
  68. #include "frame.h"
  69. #include "vector.h"
  70. #include "povproto.h"
  71.  
  72. #ifdef DB_CODE
  73.   /* Changes necessary for the vista/light buffer. */
  74.   /* I've moved the following structures to frame.h because they
  75.      are used in addon1.c. */
  76. #else
  77.   typedef struct {
  78.   int x,y,z ;
  79.   }
  80. VECTORI, *pVECTORI ;
  81.  
  82.   typedef struct {
  83.   VECTOR slab_num ;
  84.   VECTOR slab_den ;
  85.   VECTORI nonzero ;
  86.   VECTORI positive ;
  87.   }
  88. RAYINFO, *pRAYINFO ;
  89. #endif
  90.  
  91.  
  92. extern FRAME Frame;
  93. extern long Bounds_Threshold;
  94. extern int Use_Slabs;
  95. static int Axis = 0;
  96. static unsigned long maxprimcount = 0;
  97.  
  98. #ifdef DB_CODE
  99.   /* Changes necessary for the vista/light buffer. */
  100.   /* I've moved the following structure to frame.h because they
  101.      are used in addon1.c */
  102. #else
  103.   typedef struct t_qelem {
  104.   DBL     q_key;
  105.   OBJECT *q_obj;
  106.   }
  107. Qelem;
  108. #endif
  109.  
  110. static int FindAxis PARAMS((OBJECT **Prims, unsigned long first,
  111. unsigned long last));
  112. static COMPOSITE *Create_Composite PARAMS((void));
  113. static int SortAndSplit PARAMS((OBJECT **Root, OBJECT **Prims,
  114. unsigned long *nPrims, unsigned long first, unsigned long last));
  115. #ifdef DB_CODE
  116.   /* Changes necessary for the vista/light buffer. */
  117.   /* I need this functions in addon1.c and moved the headers into povproto.h */
  118. #else
  119. static void PriorityQueueInsert PARAMS((Qelem *Queue, unsigned *Qsize,
  120. DBL key, OBJECT *obj));
  121. static void CheckAndEnqueue PARAMS((Qelem *Queue, unsigned *Qsize,
  122. OBJECT *obj, RAYINFO *rayinfo));
  123. static void PriorityQueueDelete PARAMS((Qelem *Queue, unsigned *Qsize,
  124. DBL *key, OBJECT **obj));
  125. #endif
  126. /* QSORT_FUNCT_RET compslabs PARAMS((QSORT_FUNCT_PARAM in_a,
  127. QSORT_FUNCT_PARAM in_b)); */
  128.  
  129. /* Should move these out of here... */
  130. unsigned long totalQueues = 0;
  131. unsigned long totalQueueResets = 0;
  132. unsigned long nChecked = 0;
  133. unsigned long nEnqueued = 0;
  134.  
  135. unsigned MAXQUEUE = 512;
  136.  
  137. METHODS Composite_Methods =
  138.   {
  139.   NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, Destroy_Composite
  140. };
  141.  
  142. void Destroy_Composite (Object)
  143. OBJECT *Object;
  144.   {
  145.   free (Object);
  146.   }
  147.  
  148. static COMPOSITE *Create_Composite ()
  149.   {
  150.   COMPOSITE *New;
  151.  
  152.   if ((New = (COMPOSITE *) malloc (sizeof (COMPOSITE))) == NULL)
  153.     MAError ("composite");
  154.  
  155.   INIT_OBJECT_FIELDS(New, COMPOSITE_OBJECT, &Composite_Methods)
  156.     return New;
  157.   }
  158.  
  159. void
  160. recompute_bbox(bbox, trans)
  161. BBOX *bbox;
  162. TRANSFORM *trans;
  163.   {
  164.   VECTOR lower_left, lengths, corner;
  165.   VECTOR mins, maxs;
  166.   int i;
  167.  
  168.   lower_left = bbox->Lower_Left;
  169.   lengths    = bbox->Lengths;
  170.   Make_Vector(&mins,  BOUND_HUGE,  BOUND_HUGE,  BOUND_HUGE);
  171.   Make_Vector(&maxs, -BOUND_HUGE, -BOUND_HUGE, -BOUND_HUGE);
  172.   for (i=1;i<=8;i++)
  173.     {
  174.     corner = lower_left;
  175.     corner.x += ((i & 1) ? lengths.x : 0.0);
  176.     corner.y += ((i & 2) ? lengths.y : 0.0);
  177.     corner.z += ((i & 4) ? lengths.z : 0.0);
  178.     MTransPoint(&corner, &corner, trans);
  179.     if (corner.x < mins.x) mins.x = corner.x;
  180.     if (corner.x > maxs.x) maxs.x = corner.x;
  181.     if (corner.y < mins.y) mins.y = corner.y;
  182.     if (corner.y > maxs.y) maxs.y = corner.y;
  183.     if (corner.z < mins.z) mins.z = corner.z;
  184.     if (corner.z > maxs.z) maxs.z = corner.z;
  185.     }
  186.   bbox->Lower_Left = mins;
  187.   VSub(bbox->Lengths, maxs, mins);
  188.   }
  189.  
  190. void
  191. Recompute_Inverse_BBox(bbox, trans)
  192. BBOX *bbox;
  193. TRANSFORM *trans;
  194.   {
  195.   VECTOR lower_left, lengths, corner;
  196.   VECTOR mins, maxs;
  197.   int i;
  198.  
  199.   lower_left = bbox->Lower_Left;
  200.   lengths = bbox->Lengths;
  201.   Make_Vector(&mins,  BOUND_HUGE,  BOUND_HUGE,  BOUND_HUGE);
  202.   Make_Vector(&maxs, -BOUND_HUGE, -BOUND_HUGE, -BOUND_HUGE);
  203.   for (i=1;i<=8;i++)
  204.     {
  205.     corner = lower_left;
  206.     corner.x += ((i & 1) ? lengths.x : 0.0);
  207.     corner.y += ((i & 2) ? lengths.y : 0.0);
  208.     corner.z += ((i & 4) ? lengths.z : 0.0);
  209.     MInvTransPoint(&corner, &corner, trans);
  210.     if (corner.x < mins.x) mins.x = corner.x;
  211.     if (corner.x > maxs.x) maxs.x = corner.x;
  212.     if (corner.y < mins.y) mins.y = corner.y;
  213.     if (corner.y > maxs.y) maxs.y = corner.y;
  214.     if (corner.z < mins.z) mins.z = corner.z;
  215.     if (corner.z > maxs.z) maxs.z = corner.z;
  216.     }
  217.   bbox->Lower_Left = mins;
  218.   VSub(bbox->Lengths, maxs, mins);
  219.   }
  220.  
  221. QSORT_FUNCT_RET compslabs(in_a, in_b)
  222. QSORT_FUNCT_PARAM in_a;
  223. QSORT_FUNCT_PARAM in_b;
  224.   {
  225.  
  226.   OBJECT **a, **b;
  227.   DBL am, bm;
  228.  
  229.   a = (OBJECT **)in_a;
  230.   b = (OBJECT **)in_b;
  231.  
  232.   switch (Axis) 
  233.   {
  234.   case 0:
  235.     am = 2.0 * (*a)->Bounds.Lower_Left.x + (*a)->Bounds.Lengths.x;
  236.     bm = 2.0 * (*b)->Bounds.Lower_Left.x + (*b)->Bounds.Lengths.x;
  237.     break;
  238.   case 1:
  239.     am = 2.0 * (*a)->Bounds.Lower_Left.y + (*a)->Bounds.Lengths.y;
  240.     bm = 2.0 * (*b)->Bounds.Lower_Left.y + (*b)->Bounds.Lengths.y;
  241.     break;
  242.   case 2:
  243.     am = 2.0 * (*a)->Bounds.Lower_Left.z + (*a)->Bounds.Lengths.z;
  244.     bm = 2.0 * (*b)->Bounds.Lower_Left.z + (*b)->Bounds.Lengths.z;
  245.     break;
  246.   default:
  247.     Error("Bad axis in compslabs\n");
  248.   }
  249.  
  250.   if (am < bm)
  251.     return -1;
  252.   else if (am == bm)
  253.     return 0;
  254.   else
  255.     return 1;
  256.   }
  257.  
  258. static int
  259. FindAxis(Prims, first, last)
  260. OBJECT **Prims;
  261. unsigned long first, last;
  262.   {
  263.   BBOX *bbox;
  264.   VECTOR mins, maxs;
  265.   unsigned long i;
  266.   int which;
  267.   DBL d = -BOUND_HUGE, e;
  268.  
  269.   Make_Vector(&mins, BOUND_HUGE, BOUND_HUGE, BOUND_HUGE);
  270.   Make_Vector(&maxs, -BOUND_HUGE, -BOUND_HUGE, -BOUND_HUGE);
  271.  
  272.   for (i=first;i<last;i++)
  273.     {
  274.     bbox = &(Prims[i]->Bounds);
  275.     if (bbox->Lower_Left.x < mins.x)
  276.       mins.x = bbox->Lower_Left.x;
  277.     if (bbox->Lower_Left.x + bbox->Lengths.x > maxs.x)
  278.       maxs.x = bbox->Lower_Left.x;
  279.     if (bbox->Lower_Left.y < mins.y)
  280.       mins.y = bbox->Lower_Left.y;
  281.     if (bbox->Lower_Left.y + bbox->Lengths.y > maxs.y)
  282.       maxs.y = bbox->Lower_Left.y;
  283.     if (bbox->Lower_Left.z < mins.z)
  284.       mins.z = bbox->Lower_Left.z;
  285.     if (bbox->Lower_Left.z + bbox->Lengths.z > maxs.z)
  286.       maxs.z = bbox->Lower_Left.z;
  287.     }
  288.  
  289.   e = maxs.x - mins.x;
  290.   if (e > d)
  291.     {
  292.     d = e; which = 0;
  293.   }
  294.   e = maxs.y - mins.y;
  295.   if (e > d)
  296.     {
  297.     d = e; which = 1;
  298.   }
  299.   e = maxs.z - mins.z;
  300.   if (e > d) 
  301.     { 
  302.     d = e; which = 2; 
  303.   }
  304.  
  305.   return which;
  306.   }
  307.  
  308. static int
  309. SortAndSplit(Root, Prims, nPrims, first, last)
  310. OBJECT **Root;
  311. OBJECT **Prims;
  312. unsigned long *nPrims;
  313. unsigned long first;
  314. unsigned long last;
  315.   {
  316.   COMPOSITE *cd;
  317.   unsigned long size, i, j, m;
  318.   DBL dmin, dmax, tmin, tmax;
  319.  
  320.   Axis = FindAxis(Prims, first, last);
  321.   size = last - first;
  322.  
  323.   /* Actually, we could do this faster in several ways. we could use a
  324.       logn algorithm to find the median along the given axis, and then a
  325.       linear algorithm to partition along the axis. Oh well. */
  326.  
  327.   qsort((char *) (Prims + first), (int)size, sizeof(OBJECT *), compslabs);
  328.  
  329.   if (size <= BUNCHING_FACTOR) 
  330.     {
  331.     cd = Create_Composite();
  332.     cd->Entries = (unsigned short)size;
  333.  
  334.     for (i=0;i<size;i++) 
  335.       {
  336.       cd->Objects[i] = Prims[first+i];
  337. /*
  338. printf("Extent of object %ld/%d: <%g, %g, %g> -> <%g, %g, %g>\n",
  339.        first+i, cd->Objects[i]->Type,
  340.        cd->Objects[i]->Bounds.Lower_Left.x,
  341.        cd->Objects[i]->Bounds.Lower_Left.y,
  342.        cd->Objects[i]->Bounds.Lower_Left.z,
  343.        cd->Objects[i]->Bounds.Lower_Left.x + cd->Objects[i]->Bounds.Lengths.x,
  344.        cd->Objects[i]->Bounds.Lower_Left.y + cd->Objects[i]->Bounds.Lengths.y,
  345.        cd->Objects[i]->Bounds.Lower_Left.z + cd->Objects[i]->Bounds.Lengths.z);
  346. */
  347.       }
  348.  
  349.     /* Check bounds in each direction */
  350.     /* First along the x axis */
  351.     dmin = BOUND_HUGE; dmax = -BOUND_HUGE;
  352.     for (j=0;j<size;j++) 
  353.       {
  354.       tmin = cd->Objects[j]->Bounds.Lower_Left.x;
  355.       tmax = tmin + cd->Objects[j]->Bounds.Lengths.x;
  356.       if (tmin < dmin) dmin = tmin;
  357.       if (tmax > dmax) dmax = tmax;
  358.       }
  359.     cd->Bounds.Lower_Left.x = dmin;
  360.     cd->Bounds.Lengths.x = dmax - dmin;
  361.  
  362.     /* Now along the y axis */
  363.     dmin = BOUND_HUGE; dmax = -BOUND_HUGE;
  364.     for (j=0;j<size;j++)
  365.       {
  366.       tmin = cd->Objects[j]->Bounds.Lower_Left.y;
  367.       tmax = tmin + cd->Objects[j]->Bounds.Lengths.y;
  368.       if (tmin < dmin) dmin = tmin;
  369.       if (tmax > dmax) dmax = tmax;
  370.       }
  371.     cd->Bounds.Lower_Left.y = dmin;
  372.     cd->Bounds.Lengths.y = dmax - dmin;
  373.  
  374.     /* Lastly along the z axis */
  375.     dmin = BOUND_HUGE; dmax = -BOUND_HUGE;
  376.     for (j=0;j<size;j++) 
  377.       {
  378.       tmin = cd->Objects[j]->Bounds.Lower_Left.z;
  379.       tmax = tmin + cd->Objects[j]->Bounds.Lengths.z;
  380.       if (tmin < dmin) dmin = tmin;
  381.       if (tmax > dmax) dmax = tmax;
  382.       }
  383.     cd->Bounds.Lower_Left.z = dmin;
  384.     cd->Bounds.Lengths.z = dmax - dmin;
  385.  
  386.     *Root = (OBJECT *)cd;
  387.     if (*nPrims <= maxprimcount) 
  388.       {
  389.       Prims[*nPrims] = (OBJECT *)cd;
  390.       *nPrims += 1;
  391.       return 1;
  392.       }
  393.     else
  394.       Error("Too many primitives\n");
  395.     }
  396.   else 
  397.     {
  398.     m = (first + last) / 2;
  399.     SortAndSplit(Root, Prims, nPrims, first, m);
  400.     SortAndSplit(Root, Prims, nPrims, m , last);
  401.     return 0;
  402.     }
  403.   return -1;
  404.   }
  405.  
  406.   void
  407.   BuildBoundingSlabs(Root)
  408.     OBJECT **Root;
  409.   {
  410.   OBJECT **Prims, **prim, *head;
  411.   unsigned long nPrims;
  412.   unsigned long low, high;
  413.  
  414.   /* We have to start by counting how many frame level object there are */
  415.   head   = Frame.Objects;
  416.   nPrims = 0;
  417.   while (head != NULL)
  418.     {
  419.     nPrims++;
  420.     head = head->Sibling;
  421.     }
  422.  
  423.   /* The total # of prims inflates around 150% when bounding objects are
  424.       generated.  If the 1.8 below proves to be too small, use 2.0.  The
  425.       inflation is never 200%. */
  426.   maxprimcount = (unsigned long)(1.8 * (nPrims + 1));
  427.  
  428.   /* Now allocate an array to hold references to these prims & any new
  429.      composite objects we may generate */
  430.   Prims = (OBJECT **)malloc((unsigned)maxprimcount * sizeof(OBJECT *));
  431.   if (Prims == NULL)
  432.     Error("Failed to allocate bounding slab reference information\n");
  433.  
  434.   /* Copy pointers to the objects into the array */
  435.   prim = Prims;
  436.   for (head=Frame.Objects;head!=NULL;head=head->Sibling)
  437.     {
  438.     if (head->Type & LIGHT_SOURCE_OBJECT)
  439.       {
  440.       /* Only bother with lights if they have an attached shape */
  441.       if (((LIGHT_SOURCE *)head)->Children != NULL)
  442.     *prim++ = ((LIGHT_SOURCE *)head)->Children;
  443.       else
  444.     nPrims--;
  445.       }
  446.     else
  447.       /* Normal sort of object - add it to the list */
  448.       *prim++ = head;
  449.     }
  450.  
  451.   /* Now do a sort on the objects, with the end result being a tree of
  452.       objects sorted along the x, y, and z axes */
  453.   low  = 0;
  454.   high = nPrims;
  455.   while (SortAndSplit(Root, Prims, &nPrims, low, high) == 0)
  456.     {
  457.     low  = high;
  458.     high = nPrims;
  459.     }
  460.  
  461.   Use_Slabs = (nPrims >= Bounds_Threshold);
  462.  
  463.   /* Test */
  464. /*
  465. printf("Extent of scene: <%g, %g, %g> -> <%g, %g, %g>\n",
  466.        (*Root)->Bounds.Lower_Left.x,
  467.        (*Root)->Bounds.Lower_Left.y,
  468.        (*Root)->Bounds.Lower_Left.z,
  469.        (*Root)->Bounds.Lower_Left.x + (*Root)->Bounds.Lengths.x,
  470.        (*Root)->Bounds.Lower_Left.y + (*Root)->Bounds.Lengths.y,
  471.        (*Root)->Bounds.Lower_Left.z + (*Root)->Bounds.Lengths.z);
  472. */
  473.  
  474.   /* Now we can get rid of the Prim array, and just use Root */
  475.   free(Prims);
  476.   }
  477.  
  478. #ifdef DB_CODE
  479. /* Changes necessary for the vista/light buffer. */
  480. /* This has to be global */
  481. void PriorityQueueInsert(Queue, Qsize, key, obj)
  482. #else
  483. static void
  484. PriorityQueueInsert(Queue, Qsize, key, obj)
  485. #endif
  486. Qelem *Queue;
  487. unsigned *Qsize;
  488. DBL key;
  489. OBJECT *obj;
  490.   {
  491.   unsigned size;
  492.   int i;
  493.   Qelem tmp;
  494.  
  495.   totalQueues++;
  496.   (*Qsize)++;
  497.   size = *Qsize;
  498.   /* if (size > maxQueueSize) maxQueueSize = size; */
  499.   if (size >= MAXQUEUE)
  500.     Error("Priority queue overflow");
  501.   Queue[size].q_key = key;
  502.   Queue[size].q_obj = obj;
  503.  
  504.   i = size;
  505.   while (i > 1 && Queue[i].q_key < Queue[i/2].q_key)
  506.     {
  507.     tmp = Queue[i];
  508.     Queue[i] = Queue[i/2];
  509.     Queue[i/2] = tmp;
  510.     i = i / 2;
  511.     }
  512.   }
  513.  
  514. #ifdef DB_CODE
  515. /* Changes necessary for the vista/light buffer. */
  516. /* This has to be global */
  517. void PriorityQueueDelete(Queue, Qsize, key, obj)
  518. #else
  519. static void
  520. PriorityQueueDelete(Queue, Qsize, key, obj)
  521. #endif
  522. Qelem *Queue;
  523. unsigned *Qsize;
  524. DBL *key;
  525. OBJECT **obj;
  526.   {
  527.   Qelem tmp;
  528.   int i, j;
  529.   unsigned size;
  530.  
  531.   if (*Qsize == 0)
  532.     Error("priority queue is empty");
  533.  
  534.   *key = Queue[1].q_key;
  535.   *obj = Queue[1].q_obj;
  536.   Queue[1] = Queue[*Qsize];
  537.   (*Qsize)--;
  538.   size = *Qsize;
  539.  
  540.   i = 1 ;
  541.  
  542.   while (2 * i <= (int)size)
  543.     {
  544.     if (2 * i == (int)size)
  545.       j = 2 * i;
  546.     else if (Queue[2*i].q_key < Queue[2*i+1].q_key)
  547.       j = 2 * i;
  548.     else
  549.       j = 2 * i + 1;
  550.  
  551.     if (Queue[i].q_key > Queue[j].q_key)
  552.       {
  553.       tmp = Queue[i];
  554.       Queue[i] = Queue[j];
  555.       Queue[j] = tmp;
  556.       i = j;
  557.       }
  558.     else
  559.       break;
  560.     }
  561.   }
  562.  
  563. #ifdef DB_CODE
  564. /* Changes necessary for the vista/light buffer. */
  565. /* I have to pass the bouding slab seperatly, otherwise I couldn't use
  566.    this function in addon1.c */
  567. void CheckAndEnqueue(Queue, Qsize, obj, Bounds, rayinfo)
  568. #else
  569. static void
  570. CheckAndEnqueue(Queue, Qsize, obj, rayinfo)
  571. #endif
  572. Qelem *Queue;
  573. unsigned *Qsize;
  574. OBJECT *obj;
  575. #ifdef DB_CODE
  576. /* Changes necessary for the vista/light buffer. */
  577. BBOX *Bounds;
  578. #endif
  579. RAYINFO *rayinfo;
  580.   {
  581.   DBL tmin, tmax;
  582.   DBL dmin, dmax ;
  583.  
  584.   nChecked++;
  585.  
  586. #ifdef DB_CODE
  587. /* Changes necessary for the vista/light buffer. */
  588. /* Just changed obj->Bounds to Bounds */
  589.   if (rayinfo->nonzero.x )
  590.     {
  591.     if (rayinfo->positive.x )
  592.       {
  593.       dmin = (Bounds->Lower_Left.x - rayinfo->slab_num.x) *
  594.       rayinfo->slab_den.x;
  595.       dmax = dmin + (Bounds->Lengths.x  * rayinfo->slab_den.x);
  596.       if ( dmax < EPSILON ) return ;
  597.       }
  598.     else
  599.       {
  600.       dmax = (Bounds->Lower_Left.x - rayinfo->slab_num.x) *
  601.     rayinfo->slab_den.x;
  602.       if ( dmax < EPSILON ) return ;
  603.       dmin = dmax + (Bounds->Lengths.x  * rayinfo->slab_den.x);
  604.       }
  605.     if ( dmin > dmax ) return ;
  606.     }
  607.   else
  608.     {
  609.     if ( ( rayinfo->slab_num.x < Bounds->Lower_Left.x ) ||
  610.       ( rayinfo->slab_num.x >
  611.       Bounds->Lengths.x + Bounds->Lower_Left.x ) ) return ;
  612.     dmin = -BOUND_HUGE; dmax = BOUND_HUGE;
  613.     }
  614.  
  615.   if (rayinfo->nonzero.y )
  616.     {
  617.     if (rayinfo->positive.y )
  618.       {
  619.       tmin = (Bounds->Lower_Left.y - rayinfo->slab_num.y) *
  620.       rayinfo->slab_den.y;
  621.       tmax = tmin + (Bounds->Lengths.y  * rayinfo->slab_den.y);
  622.       }
  623.     else
  624.       {
  625.       tmax = (Bounds->Lower_Left.y - rayinfo->slab_num.y) *
  626.     rayinfo->slab_den.y;
  627.       tmin = tmax + (Bounds->Lengths.y  * rayinfo->slab_den.y);
  628.       }
  629.     /* unwrap the logic - do the dmin and dmax checks only when tmin and
  630.       tmax actually affect anything, also try to escape ASAP.  Better
  631.       yet, fold the logic below into the two branches above so as to
  632.       compute only what is needed.
  633.     */
  634.     /* you might even try tmax < EPSILON first (instead of second) for an
  635.       early quick out
  636.     */
  637.     if ( tmax < dmax )
  638.       {
  639.       if ( tmax < EPSILON ) return;
  640.       /* check bounds only if tmax changes dmax */
  641.       if ( tmin > dmin )
  642.     {
  643.     if ( tmin > tmax ) return ;
  644.     /* do this last in case it's not needed! */
  645.     dmin = tmin ;
  646.     }
  647.       else
  648.     {
  649.     if ( dmin > tmax ) return ;
  650.     }
  651.       /* do this last in case it's not needed! */
  652.       dmax = tmax ;
  653.       }
  654.     else
  655.       {
  656.       if ( tmin > dmin )
  657.     {
  658.     if ( tmin > dmax ) return ;
  659.     /* do this last in case it's not needed! */
  660.     dmin = tmin ;
  661.     } /* else nothing needs to happen, since dmin and dmax did not
  662.            change! */
  663.  
  664.       }
  665.     }
  666.   else
  667.     {
  668.     if (rayinfo->slab_num.y < Bounds->Lower_Left.y ||
  669.       rayinfo->slab_num.y >
  670.       Bounds->Lengths.y + Bounds->Lower_Left.y ) return ;
  671.     }
  672.  
  673.   if (rayinfo->nonzero.z )
  674.     {
  675.     if (rayinfo->positive.z )
  676.       {
  677.       tmin = (Bounds->Lower_Left.z - rayinfo->slab_num.z) *
  678.       rayinfo->slab_den.z;
  679.       tmax = tmin + (Bounds->Lengths.z  * rayinfo->slab_den.z);
  680.       }
  681.     else
  682.       {
  683.       tmax = (Bounds->Lower_Left.z - rayinfo->slab_num.z) *
  684.     rayinfo->slab_den.z;
  685.       tmin = tmax + (Bounds->Lengths.z  * rayinfo->slab_den.z);
  686.       }
  687.     if ( tmax < dmax )
  688.       {
  689.       if ( tmax < EPSILON ) return;
  690.       /* check bounds only if tmax changes dmax */
  691.       if ( tmin > dmin )
  692.     {
  693.     if ( tmin > tmax ) return ;
  694.     /* do this last in case it's not needed! */
  695.     dmin = tmin ;
  696.     }
  697.       else
  698.     {
  699.     if ( dmin > tmax ) return ;
  700.     }
  701.       /* do this last in case it's not needed! */
  702.       dmax = tmax ;
  703.       }
  704.     else
  705.       {
  706.       if ( tmin > dmin )
  707.     {
  708.     if ( tmin > dmax ) return ;
  709.     /* do this last in case it's not needed! */
  710.     dmin = tmin ;
  711.     } /* else nothing needs to happen, since dmin and dmax did not
  712.            change! */
  713.  
  714.       }
  715.     }
  716.   else
  717.     {
  718.     if (rayinfo->slab_num.z < Bounds->Lower_Left.z ||
  719.       rayinfo->slab_num.z >
  720.       Bounds->Lengths.z + Bounds->Lower_Left.z ) return ;
  721.     }
  722. #else
  723.   if (rayinfo->nonzero.x )
  724.     {
  725.     if (rayinfo->positive.x )
  726.       {
  727.       dmin = (obj->Bounds.Lower_Left.x - rayinfo->slab_num.x) *
  728.       rayinfo->slab_den.x;
  729.       dmax = dmin + (obj->Bounds.Lengths.x  * rayinfo->slab_den.x);
  730.       if ( dmax < EPSILON ) return ;
  731.       }
  732.     else
  733.       {
  734.       dmax = (obj->Bounds.Lower_Left.x - rayinfo->slab_num.x) *
  735.     rayinfo->slab_den.x;
  736.       if ( dmax < EPSILON ) return ;
  737.       dmin = dmax + (obj->Bounds.Lengths.x  * rayinfo->slab_den.x);
  738.       }
  739.     if ( dmin > dmax ) return ;
  740.     }
  741.   else
  742.     {
  743.     if ( ( rayinfo->slab_num.x < obj->Bounds.Lower_Left.x ) ||
  744.       ( rayinfo->slab_num.x >
  745.       obj->Bounds.Lengths.x + obj->Bounds.Lower_Left.x ) ) return ;
  746.     dmin = -BOUND_HUGE; dmax = BOUND_HUGE;
  747.     }
  748.  
  749.   if (rayinfo->nonzero.y )
  750.     {
  751.     if (rayinfo->positive.y )
  752.       {
  753.       tmin = (obj->Bounds.Lower_Left.y - rayinfo->slab_num.y) *
  754.       rayinfo->slab_den.y;
  755.       tmax = tmin + (obj->Bounds.Lengths.y  * rayinfo->slab_den.y);
  756.       }
  757.     else
  758.       {
  759.       tmax = (obj->Bounds.Lower_Left.y - rayinfo->slab_num.y) *
  760.     rayinfo->slab_den.y;
  761.       tmin = tmax + (obj->Bounds.Lengths.y  * rayinfo->slab_den.y);
  762.       }
  763.     /* unwrap the logic - do the dmin and dmax checks only when tmin and
  764.       tmax actually affect anything, also try to escape ASAP.  Better
  765.       yet, fold the logic below into the two branches above so as to
  766.       compute only what is needed.
  767.     */
  768.     /* you might even try tmax < EPSILON first (instead of second) for an
  769.       early quick out
  770.     */
  771.     if ( tmax < dmax )
  772.       {
  773.       if ( tmax < EPSILON ) return;
  774.       /* check bounds only if tmax changes dmax */
  775.       if ( tmin > dmin )
  776.     {
  777.     if ( tmin > tmax ) return ;
  778.     /* do this last in case it's not needed! */
  779.     dmin = tmin ;
  780.     }
  781.       else
  782.     {
  783.     if ( dmin > tmax ) return ;
  784.     }
  785.       /* do this last in case it's not needed! */
  786.       dmax = tmax ;
  787.       }
  788.     else
  789.       {
  790.       if ( tmin > dmin )
  791.     {
  792.     if ( tmin > dmax ) return ;
  793.     /* do this last in case it's not needed! */
  794.     dmin = tmin ;
  795.     } /* else nothing needs to happen, since dmin and dmax did not
  796.            change! */
  797.  
  798.       }
  799.     }
  800.   else
  801.     {
  802.     if (rayinfo->slab_num.y < obj->Bounds.Lower_Left.y ||
  803.       rayinfo->slab_num.y >
  804.       obj->Bounds.Lengths.y + obj->Bounds.Lower_Left.y ) return ;
  805.     }
  806.  
  807.   if (rayinfo->nonzero.z )
  808.     {
  809.     if (rayinfo->positive.z )
  810.       {
  811.       tmin = (obj->Bounds.Lower_Left.z - rayinfo->slab_num.z) *
  812.       rayinfo->slab_den.z;
  813.       tmax = tmin + (obj->Bounds.Lengths.z  * rayinfo->slab_den.z);
  814.       }
  815.     else
  816.       {
  817.       tmax = (obj->Bounds.Lower_Left.z - rayinfo->slab_num.z) *
  818.     rayinfo->slab_den.z;
  819.       tmin = tmax + (obj->Bounds.Lengths.z  * rayinfo->slab_den.z);
  820.       }
  821.     if ( tmax < dmax )
  822.       {
  823.       if ( tmax < EPSILON ) return;
  824.       /* check bounds only if tmax changes dmax */
  825.       if ( tmin > dmin )
  826.     {
  827.     if ( tmin > tmax ) return ;
  828.     /* do this last in case it's not needed! */
  829.     dmin = tmin ;
  830.     }
  831.       else
  832.     {
  833.     if ( dmin > tmax ) return ;
  834.     }
  835.       /* do this last in case it's not needed! */
  836.       dmax = tmax ;
  837.       }
  838.     else
  839.       {
  840.       if ( tmin > dmin )
  841.     {
  842.     if ( tmin > dmax ) return ;
  843.     /* do this last in case it's not needed! */
  844.     dmin = tmin ;
  845.     } /* else nothing needs to happen, since dmin and dmax did not
  846.            change! */
  847.  
  848.       }
  849.     }
  850.   else
  851.     {
  852.     if (rayinfo->slab_num.z < obj->Bounds.Lower_Left.z ||
  853.       rayinfo->slab_num.z >
  854.       obj->Bounds.Lengths.z + obj->Bounds.Lower_Left.z ) return ;
  855.     }
  856. #endif
  857.  
  858.   PriorityQueueInsert(Queue, Qsize, dmin, obj);
  859.   nEnqueued++;
  860.   }
  861.  
  862. int
  863. Bounds_Intersect(Root, ray, Best_Intersection, Best_Object)
  864. OBJECT *Root;
  865. RAY *ray;
  866. INTERSECTION *Best_Intersection;
  867. OBJECT **Best_Object;
  868.   {
  869.   Qelem *Queue;
  870.   unsigned Qsize = 0;
  871.   int i;
  872.   OBJECT *cobj;
  873.   COMPOSITE *cdp;
  874.   RAYINFO rayinfo;
  875.   DBL t, key;
  876.   INTERSECTION New_Intersection;
  877.   int Intersection_Found = 0;
  878.  
  879.   Queue = (Qelem *)malloc(MAXQUEUE * sizeof(Qelem));
  880.   if (Queue == NULL)
  881.     Error("Failed to allocate priority queue\n");
  882.  
  883.   /* Create the direction vectors for this ray */
  884.   rayinfo.slab_num.x = ray->Initial.x;
  885.   rayinfo.slab_num.y = ray->Initial.y;
  886.   rayinfo.slab_num.z = ray->Initial.z;
  887.   if ( rayinfo.nonzero.x = ((t = ray->Direction.x) != 0.0) )
  888.     {
  889.     rayinfo.slab_den.x = 1.0 / t;
  890.     rayinfo.positive.x = ( ray->Direction.x > 0.0 ) ;
  891.     }
  892.   if ( rayinfo.nonzero.y = ((t = ray->Direction.y) != 0.0) )
  893.     {
  894.     rayinfo.slab_den.y = 1.0 / t;
  895.     rayinfo.positive.y = ( ray->Direction.y > 0.0 ) ;
  896.     }
  897.   if ( rayinfo.nonzero.z = ((t = ray->Direction.z) != 0.0) )
  898.     {
  899.     rayinfo.slab_den.z = 1.0 / t;
  900.     rayinfo.positive.z = ( ray->Direction.z > 0.0 ) ;
  901.     }
  902.  
  903.   /* start with an empty priority queue */
  904.   Qsize = 0;
  905.   totalQueueResets++;
  906.  
  907. #ifdef DB_CODE
  908.   /* Changes necessary for the vista/light buffer. */
  909.   /* Pass bounds seperatly */
  910.   CheckAndEnqueue(Queue, &Qsize, Root, &Root->Bounds, &rayinfo);
  911. #else
  912.   CheckAndEnqueue(Queue, &Qsize, Root, &rayinfo);
  913. #endif
  914.  
  915.   for (;;)
  916.     {
  917.     if (Qsize == 0)
  918.       break;
  919.  
  920.     PriorityQueueDelete(Queue, &Qsize, &key, &cobj);
  921.  
  922.     if (key > Best_Intersection->Depth)
  923.       break;
  924.     else
  925.       if (cobj->Type & BOUNDING_OBJECT)
  926.     {
  927.     cdp = (COMPOSITE *)cobj;
  928.     for (i=0;(unsigned short)i < cdp->Entries;i++)
  929. #ifdef DB_CODE
  930.       /* Changes necessary for the vista/light buffer. */
  931.       /* Pass bounds seperatly */
  932.       CheckAndEnqueue(Queue, &Qsize, cdp->Objects[i], &cdp->Objects[i]->Bounds, &rayinfo);
  933. #else
  934.       CheckAndEnqueue(Queue, &Qsize, cdp->Objects[i],
  935.         &rayinfo) ;
  936. #endif
  937.     }
  938.       else
  939.     {
  940.     if (Intersection(&New_Intersection, cobj, ray))
  941.       if (New_Intersection.Depth < Best_Intersection->Depth)
  942.         {
  943.         *Best_Intersection = New_Intersection;
  944.         *Best_Object = cobj;
  945.         Intersection_Found = TRUE;
  946.         }
  947.     }
  948.     }
  949.  
  950.   free(Queue);
  951.   return Intersection_Found;
  952.   }
  953.